<?php
/**
 * @title 147. 对链表进行插入排序 - 迭代
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function insertionSortList($head) {
        if($head === null){
            return null;
        } else {}

        /**
         * @since 2020-08-07 迭代
         */
        $list = new ListNode(null);
        $list->next = $head;
        $listArray = [$list];

        while($head !== null){
            $listArray[] = $head;
            $head = $head->next;
        }
        // return $listArray;

        /**
         * @since 2020-08-07 调整链表
         */
        for ($i=2, $len=count($listArray); $i <= $len-1; $i++){
            /**
             * @since 2020-08-07 节点b, c
             */
            $b = $listArray[$i-1];
            $c = $listArray[$i];

            /**
             * @since 2020-08-07 b<c, 不需要移动
             */
            if($b->val <= $c->val){
                continue;
            } else {
                /**
                 * @since 2020-08-07 链表a->b->c->d 改成a->b->d
                 */
                $b->next = $c->next;

                /**
                 * @since 2020-08-07 b顶替c的位置
                 */
                $listArray[$i] = $b;

                /**
                 * @since 2020-08-07 沿链表往上比较
                 */
                for($j=$i-2; $j>=1; $j--){
                    $a = $listArray[$j];

                    /**
                     * @since 2020-08-07 a<c
                     */
                    if($a->val <= $c->val){
                        /**
                         * @since 2020-08-07 c插入a->b
                         */
                        $c->next = $a->next;
                        $a->next = $c;

                        /**
                         * @since 2020-08-07 c顶替b的位置
                         */
                        $listArray[$j+1] = $c;

                        /**
                         * @since 2020-08-07 break
                         */
                        break;
                    } else {
                        /**
                         * @since 2020-08-07 链表不变, a顶替j+1位置
                         */
                        $listArray[$j+1] = $a;
                    }
                }

                /**
                 * @since 2020-08-07 收官
                 */
                if($j==0){
                    /**
                     * @since 2020-08-07 c是最大值
                     */
                    $c->next = $listArray[0]->next;
                    $listArray[0]->next = $c;
                    $listArray[1] = $c;
                } else {}
            }
        }

        /**
         * @return
         */
        return $listArray[1];
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.07_2.php
 */
$datas = [
    [4,2,1,3],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->insertionSortList($xhprof->listNode($data));
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
